Communication networks are widely used across many industries and sections of society. Such networks may include, for example, telecommunications networks, social media networks, office networks, academia networks and community networks. The use of communication networks is growing, with continual expansion of customer bases driving business growth in this sector.
Connections between users within a communication network may give rise to paths through the network, by which a user may be placed into contact with another user with whom they are have no direct connection. Network operators frequently attempt to identify such paths based on their global view of the connectivity of the network. Such paths may be sought with a view to introducing second or third hand connections to each other and so increasing the density and utility of the network. Various methods exist for identifying paths among network users, which methods may prioritise either path length or connection strength. For example, in some network configurations or situations, identifying the shortest path between a first and a second user may be important, and such a path may be identified by reflecting user connectivity on a network graph and applying a shortest path algorithm to find the shortest path between the first and second users. Examples of shortest path algorithms include Dijkstra's algorithm, the Bellman Ford algorithm and Johnson's algorithm. In other situations, a greater importance may be placed upon the strength of connection between users in the path, prioritising a longer path in which each hop is between strongly connected users over a shorter path in which one or more hops is between users sharing only a very loose connection.
Information propagation is one example application in which a strongest path may be preferred over a shortest path. In a situation in which a source user wishes to propagate a request or piece of information to a target user with whom they have no direct connection, the likelihood of each member of the path passing the information or request along is of prime importance. In such cases, the success of the path is more dependent on the strength of the individual hops than the overall path length. The nature of the communication network in which a path is sought may also have an impact upon the most appropriate method for path identification. For example, the number of options for a path between two users may be greatly reduced in a sparse network compared to a dense network. On the other hand, connection strength in a dense network may vary widely, greatly impacting the likelihood of any particular path fulfilling its purpose.
The wide range of factors which may affect path selection and identification, together with the variety in communication network configuration and the different purposes for which a network operator may wish to identify a path, have led to the development of a wide range of different techniques, optimised for particular circumstances. In such a rapidly evolving domain, these highly tailored solutions may be overtaken by developments, as new measures of user connection, and new uses and applications for communication networks are considered.